Miller-Rabin Primality Test

Module 02 / Lesson 06

Algorithm Walkthrough

Probabilistic Primality

The Miller-Rabin primality test is a probabilistic algorithm used to determine if a number is likely to be prime. It is more robust than Fermat's test because it detects Carmichael numbers (composite numbers that pass Fermat's test).

The Mathematical Process:

1. Find $n-1 = 2^k \cdot q$ where $q$ is odd.
2. Select a random witness a in range $[2, n-2]$.
3. Compute $x = a^q \pmod{n}$.
4. If $x=1$ or $x=n-1$, the number is "Probably Prime".
5. Otherwise, square $x$ repeatedly to check for $n-1$.

By repeating this test with different values of a, the probability of a composite number being labeled prime becomes effectively zero.

Python Implementation

import random

def miller_rabin(n, k=5): # k is the number of iterations
    if n <= 1: return False
    if n <= 3: return True
    if n % 2 == 0: return False

    # Write n-1 as 2^r * d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2

    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

# Test
num = 104729 # A known prime
print(f"Is {num} prime? {miller_rabin(num)}")

← Previous Lesson Back to Module Next Lesson →